import java.util.Objects;

/**
 * 965. 单值二叉树
 * <p>
 * 如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。
 * 只有给定的树是单值二叉树时，才返回 true；否则返回 false。
 * <p>
 * https://leetcode.cn/problems/univalued-binary-tree/
 */
public class isUnivalTree {

    public static void main(String[] args) {
        isUnivalTree isUnivalTree = new isUnivalTree();
        TreeNode root = new TreeNode(
                2,
                new TreeNode(2, new TreeNode(2), new TreeNode(1)),
                new TreeNode(2, null, new TreeNode(2))
        );
        System.out.println(isUnivalTree.isUnivalTree_2(root));
    }

    /**
     * 0 ms(100.00%)	38.9 MB(58.95%)
     *
     * @param root
     * @return
     */
    public boolean isUnivalTree_1(TreeNode root) {
        if (root.left != null && !isUnivalTree_1(root.left, root.val)) return false;
        return root.right == null || isUnivalTree_1(root.right, root.val);
    }

    public boolean isUnivalTree_1(TreeNode node, int val) {
        if (node == null || !Objects.equals(node.val, val)) return false;
        if (node.left != null && !isUnivalTree_1(node.left, val)) return false;
        return node.right == null || isUnivalTree_1(node.right, val);
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "val=" + val +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }

    /**
     * 更优化的解法
     * 0 ms（100.00%）	38.7 MB（95.22%）
     *
     * @param root
     * @return
     */
    public boolean isUnivalTree_2(TreeNode root) {
        if (root == null) return false;
        if (root.left != null) if (root.val != root.left.val || !isUnivalTree_2(root.left)) return false;
        if (root.right != null) if (root.val != root.right.val || !isUnivalTree_2(root.right)) return false;
        return true;
    }
}
